
import java.io.IOException;
import java.util.*;


public class Main{
    static int[] tmp = new int[100000];

    public static void main(String[] args) throws IOException{
//        Scanner scanner = new Scanner(System.in);
//        int num = scanner.nextInt();
//        int k = scanner.nextInt();
//        int[] arr = new int[num];
//        for (int i = 0; i < num; i++) {
//            arr[i] = scanner.nextInt();
//        }
        int[] arr = new int[]{5,3,4,3,2,1};
        int num = arr.length-1;
        //quickSort(arr, 0, num );
        merge_sort(arr,0,num);
            System.out.print(Arrays.toString(arr));
    }
    //闫总快排模板 v.v
    public static void quickSort(int[] arr, int l, int r) {
        if(l>=r) return ;
        int x = arr[(l+r)/2];
        int i = l-1;int j = r+1;
        while(i<j) {
            do {
                i++;
            }while(x>arr[i]);
            do {
                j--;
            }while(x<arr[j]);

            if(i<j) {
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
        quickSort(arr,l,j);
        quickSort(arr,j+1,r);
    }

    public static void merge_sort (int[] arr,int l,int r) {
        if(l>=r) return;

        int mid = (l+r)/2;

        merge_sort(arr,l,mid);merge_sort(arr,mid+1,r);
        int k = 0;
        int i = l;
        int j = mid+1;

        while(i<=mid && j<=r) {
            if(arr[i]<=arr[j]) tmp[k++] = arr[i++];
            else tmp[k++] = arr[j++];
        }
        while(i<=mid) tmp[k++] = arr[i++];
        while(j<=r) tmp[k++] = arr[j++];
        for(i = l,j = 0;i<=r;i++,j++) arr[i] = tmp[j];
        
    }
}

